package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-28 19:03
 * @description: Functions of this class is
 * 官方解法；O(1)的空间复杂度
 * class Solution {
 *     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 *         ListNode prehead = new ListNode(-1);
 *
 *         ListNode prev = prehead;
 *         while (l1 != null && l2 != null) {
 *         //下面的操作真的很妙，这样的话就不用再去创建新的节点了
 *             if (l1.val <= l2.val) {
 *                 prev.next = l1;
 *                 l1 = l1.next;
 *             } else {
 *                 prev.next = l2;
 *                 l2 = l2.next;
 *             }
 *             prev = prev.next;
 *         }
 *
 *         // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
 *         prev.next = l1 == null ? l2 : l1;
 *
 *         return prehead.next;
 *     }
 * }
 **/
public class 合并两个有序链表 {

      public class ListNode {
          int val;
          ListNode next;
         ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head=new ListNode();
        ListNode tail=head;
        while (l1 != null && l2 != null) {
            ListNode p=new ListNode();
            if (l1.val <= l2.val) {
                p.val=l1.val;
                l1 = l1.next;
            } else {
                p.val=l2.val;
                l2 = l2.next;
            }
            tail.next=p;
            tail=p;
        }
        while (l1 != null) {
            ListNode p = new ListNode(l1.val);
            l1 = l1.next;
            tail.next=p;
            tail=p;
        }
        while (l2 != null) {
            ListNode p = new ListNode(l2.val);
            l2 = l2.next;
            tail.next=p;
            tail=p;
        }
        return head.next;
    }
}